{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from scipy.stats import poisson"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "poissonContainer = {}\n",
    "\n",
    "def poisson_distribution(n, lam):\n",
    "    global poissonContainer\n",
    "    if str(n) + \",\" + str(lam) not in poissonContainer:\n",
    "        poissonContainer[str(n) + \",\" + str(lam)] = poisson.pmf(n, lam)\n",
    "    return poissonContainer[str(n) + \",\" + str(lam)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "MAX_CAR = 20\n",
    "\n",
    "RENT_LAM_FIRST_PLACE = 3\n",
    "RENT_LAM_SECOND_PLACE = 4\n",
    "RETURN_LAM_FIRST_PLACE = 3\n",
    "RETURN_LAM_SECOND_PLACE = 2\n",
    "\n",
    "RENT_REWARD_PER_CAR = 10\n",
    "\n",
    "TRANSFER_REWARD_PER_CAR = -2\n",
    "\n",
    "DISCOUNT = 0.9\n",
    "\n",
    "MAX_TRANSFER_NUMBER = 5\n",
    "\n",
    "POISSON_UPPER_BOUND = 11\n",
    "\n",
    "stateValue = np.zeros(shape = (21, 21))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def action_value(firstNumber, secondNumber, action, stateValue):\n",
    "\n",
    "    reward = 0\n",
    "    action1 = action\n",
    "    if action > 0:\n",
    "        if action > firstNumber:\n",
    "            action = firstNumber\n",
    "    else:\n",
    "        if abs(action) > secondNumber:\n",
    "            action = -secondNumber\n",
    "    nextDayFirstNumber = min(max(firstNumber - action, 0), MAX_CAR)\n",
    "    nextDaySecondNumber = min(max(secondNumber + action, 0), MAX_CAR)\n",
    "    reward += abs(action1) * TRANSFER_REWARD_PER_CAR\n",
    "\n",
    "    for i in range(POISSON_UPPER_BOUND):\n",
    "        for j in range(POISSON_UPPER_BOUND):\n",
    "            prob = poisson_distribution(i, RENT_LAM_FIRST_PLACE) * poisson_distribution(j, RENT_LAM_SECOND_PLACE)\n",
    "            validRentFirst = min(nextDayFirstNumber, i)\n",
    "            validRentSecond = min(nextDaySecondNumber, j)\n",
    "            reward += prob * (validRentFirst + validRentSecond) * RENT_REWARD_PER_CAR\n",
    "            nextDayAfterRentFirstNumber = nextDayFirstNumber - validRentFirst\n",
    "            nextDayAfterRentSecondNumber = nextDaySecondNumber - validRentSecond\n",
    "\n",
    "\n",
    "            for p in range(POISSON_UPPER_BOUND):\n",
    "                for q in range(POISSON_UPPER_BOUND):\n",
    "                    probReturn = poisson_distribution(p, RETURN_LAM_FIRST_PLACE) * poisson_distribution(q, RETURN_LAM_SECOND_PLACE)\n",
    "                    probTotal = prob * probReturn\n",
    "                    nextDayStateFirst = min(nextDayAfterRentFirstNumber + p, MAX_CAR)\n",
    "                    nextDATStateSecond = min(nextDayAfterRentSecondNumber + q, MAX_CAR)\n",
    "                    reward += probTotal * DISCOUNT * stateValue[nextDayStateFirst][nextDATStateSecond]\n",
    "    return reward"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def value_iteration(stateValue):\n",
    "    counter = 1\n",
    "    delta = 1e9\n",
    "    while delta > 1:\n",
    "        print(str(counter) + \"iteration.\")\n",
    "        oldValue = np.array(stateValue)\n",
    "        delta = 0\n",
    "        for i in range(MAX_CAR + 1):\n",
    "            for j in range(MAX_CAR + 1):\n",
    "                \n",
    "                stateValue[i][j] = action_value(i, j, -MAX_TRANSFER_NUMBER, oldValue)\n",
    "                for action in range(-MAX_TRANSFER_NUMBER + 1, MAX_TRANSFER_NUMBER + 1):\n",
    "                    stateValue[i][j] = max(stateValue[i][j], action_value(i, j, action, oldValue))\n",
    "                delta = max(delta, abs(stateValue[i][j] - oldValue[i][j]))\n",
    "        print(delta)\n",
    "        counter += 1\n",
    "    actionMatrix = np.zeros(shape = (MAX_CAR + 1, MAX_CAR + 1))\n",
    "    for i in range(MAX_CAR + 1):\n",
    "        for j in range(MAX_CAR + 1):\n",
    "            actionMatrix[i][j] = 0\n",
    "            tmpValue = action_value(i, j, 0, stateValue)\n",
    "            for action in range(-MAX_TRANSFER_NUMBER, MAX_TRANSFER_NUMBER + 1):\n",
    "                if action_value(i, j, action, stateValue) > tmpValue:\n",
    "                    actionMatrix[i][j] = action\n",
    "                    tmpValue = action_value(i, j, action, stateValue)\n",
    "    return actionMatrix\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1iteration.\n",
      "69.54493820103355\n",
      "2iteration.\n",
      "62.37569817769415\n",
      "3iteration.\n",
      "55.93405206178389\n",
      "4iteration.\n",
      "50.0476664436878\n",
      "5iteration.\n",
      "44.57056827897975\n",
      "6iteration.\n",
      "39.5270824291178\n",
      "7iteration.\n",
      "34.966607703970226\n",
      "8iteration.\n",
      "30.867973061910902\n",
      "9iteration.\n",
      "27.17835301128872\n",
      "10iteration.\n",
      "23.85879339652581\n",
      "11iteration.\n",
      "20.890382828940346\n",
      "12iteration.\n",
      "18.262136947795\n",
      "13iteration.\n",
      "15.959145455199177\n",
      "14iteration.\n",
      "13.957508326211325\n",
      "15iteration.\n",
      "12.22699294730836\n",
      "16iteration.\n",
      "10.733942511638134\n",
      "17iteration.\n",
      "9.444953277895024\n",
      "18iteration.\n",
      "8.329609825932152\n",
      "19iteration.\n",
      "7.362503190407438\n",
      "20iteration.\n",
      "6.521653603417462\n",
      "21iteration.\n",
      "5.787510738688525\n",
      "22iteration.\n",
      "5.144556015356443\n",
      "23iteration.\n",
      "4.579855521961122\n",
      "24iteration.\n",
      "4.082389317891057\n",
      "25iteration.\n",
      "3.6429126629794837\n",
      "26iteration.\n",
      "3.253721664247905\n",
      "27iteration.\n",
      "2.908338217024152\n",
      "28iteration.\n",
      "2.601275498632276\n",
      "29iteration.\n",
      "2.3278585795812887\n",
      "30iteration.\n",
      "2.0840816273341716\n",
      "31iteration.\n",
      "1.8664929362273597\n",
      "32iteration.\n",
      "1.672102224910759\n",
      "33iteration.\n",
      "1.4983058607363091\n",
      "34iteration.\n",
      "1.342826428497915\n",
      "35iteration.\n",
      "1.203663698196351\n",
      "36iteration.\n",
      "1.0790546114222934\n",
      "37iteration.\n",
      "0.9674403936041926\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[ 0.,  0.,  0.,  0.,  0.,  0.,  0., -1., -1., -1., -2., -2., -2.,\n",
       "        -3., -3., -3., -3., -4., -4., -4., -4.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0., -1., -1., -1., -2.,\n",
       "        -2., -2., -2., -3., -3., -3., -3., -3.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0., -1., -1.,\n",
       "        -1., -1., -2., -2., -2., -2., -2., -2.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0., -1., -1., -1., -1., -1., -1., -2.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0., -1., -1.],\n",
       "       [ 1.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 2.,  2.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 3.,  2.,  2.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 3.,  3.,  2.,  2.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 4.,  3.,  3.,  2.,  2.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 4.,  4.,  3.,  3.,  2.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  4.,  4.,  3.,  2.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  4.,  3.,  2.,  2.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  4.,  3.,  3.,  2.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  4.,  4.,  3.,  2.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  5.,  4.,  3.,  2.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  5.,  4.,  3.,  2.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  5.,  4.,  3.,  2.,  2.,  1.,  1.,  0.,  0.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  5.,  4.,  3.,  3.,  2.,  2.,  1.,  1.,  1.,  0.,  0.,\n",
       "         0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  5.,  4.,  4.,  3.,  3.,  2.,  2.,  2.,  1.,  1.,  1.,\n",
       "         1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 5.,  5.,  5.,  5.,  4.,  4.,  3.,  3.,  3.,  2.,  2.,  2.,  2.,\n",
       "         2.,  1.,  1.,  1.,  0.,  0.,  0.,  0.]])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "actionMatrix = value_iteration(stateValue)\n",
    "actionMatrix"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "494899efd6527d56ea7f55c588d0081523a17dc3a9ff1107f3394ad815ff2527"
  },
  "kernelspec": {
   "display_name": "Python 3.7.7 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
